{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of Square-Free Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: squareFreeSubsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无平方子集计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>如果数组 <code>nums</code> 的子集中的元素乘积是一个 <strong>无平方因子数</strong> ，则认为该子集是一个 <strong>无平方</strong> 子集。</p>\n",
    "\n",
    "<p><strong>无平方因子数</strong> 是无法被除 <code>1</code> 之外任何平方数整除的数字。</p>\n",
    "\n",
    "<p>返回数组 <code>nums</code> 中 <strong>无平方</strong> 且 <strong>非空</strong> 的子集数目。因为答案可能很大，返回对 <code>10<sup>9</sup> + 7</code> 取余的结果。</p>\n",
    "\n",
    "<p><code>nums</code> 的 <strong>非空子集</strong> 是可以由删除 <code>nums</code> 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,4,4,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>示例中有 3 个无平方子集：\n",
    "- 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ，这是一个无平方因子数。\n",
    "- 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ，这是一个无平方因子数。\n",
    "- 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ，这是一个无平方因子数。\n",
    "可以证明给定数组中不存在超过 3 个无平方子集。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>示例中有 1 个无平方子集：\n",
    "- 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。\n",
    "可以证明给定数组中不存在超过 1 个无平方子集。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 30</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-square-free-subsets](https://leetcode.cn/problems/count-the-number-of-square-free-subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-square-free-subsets](https://leetcode.cn/problems/count-the-number-of-square-free-subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,4,5]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes=2,3,5,7,11,13,17,19,23,29\n",
    "sf_to_mask=[0]*31\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i%p==0:\n",
    "            if i%(p*p)==0:\n",
    "                sf_to_mask[i]=-1\n",
    "                break\n",
    "            sf_to_mask[i] |= 1<<j\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        cnt=Counter(nums)\n",
    "        m=1<<len(primes)\n",
    "        f=[0]*m\n",
    "        # f[0]=1\n",
    "        # for x in nums:\n",
    "        #     mask=sf_to_mask[x]\n",
    "        #     if mask>=0:\n",
    "        #         for j in range(m-1,mask-1,-1):\n",
    "        #             if (j|mask)==j:\n",
    "        #                 f[j]=(f[j]+f[j^mask])%mod\n",
    "        # return (sum(f)-1)%mod\n",
    "        f[0]=pow(2,cnt[1],mod)\n",
    "        for x,c in cnt.items():\n",
    "            mask=sf_to_mask[x]\n",
    "            if mask>0:\n",
    "                j=other=(m-1)^mask\n",
    "                while True:\n",
    "                    f[j|mask]=(f[j|mask]+f[j]*c)%mod\n",
    "                    j=(j-1)&other\n",
    "                    if j==other:break\n",
    "        return (sum(f)-1)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "TO_MASK = [0] * 31\n",
    "for i in range(2, 32):\n",
    "    for k, j in enumerate(PRIMES):\n",
    "        if i % j == 0:\n",
    "            if i % (j * j) == 0:\n",
    "                TO_MASK[i] = -1\n",
    "                break\n",
    "            TO_MASK[i] |= 1 << k\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        M = 1 << 10\n",
    "        MASK = [0] * 31\n",
    "        f = [0] * M\n",
    "        f[0] = 1\n",
    "        cnt = Counter(nums)\n",
    "        for x, c in cnt.items():\n",
    "            mask = TO_MASK[x]\n",
    "            if mask > 0:\n",
    "                for other in range(M - 1, -1, -1):\n",
    "                    if (mask & other) == 0:\n",
    "                        f[mask|other] = (f[mask|other] + f[other] * c) % mod\n",
    "        return (sum(f) * pow(2, cnt[1], mod) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = 2,3,5,7,11,13,17,19,23,29\n",
    "SF_to_mask = [0]*31\n",
    "for i in range(2,31):\n",
    "    for j , p in enumerate(primes):\n",
    "        if i % p ==0:\n",
    "            if i % (p*p) == 0:\n",
    "                SF_to_mask[i] = -1\n",
    "                break\n",
    "            SF_to_mask[i] |= 1<<j            \n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        M = 1<<len(primes)\n",
    "        f = [0]*M \n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            mask = SF_to_mask[x]\n",
    "            if mask >= 0:\n",
    "                for j in range(M-1,mask-1,-1):\n",
    "                    if (j|mask) == j:\n",
    "                        f[j] = (f[j] + f[j^mask])% mod\n",
    "        return (sum(f)-1) % mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes=2,3,5,7,11,13,17,19,23,29\n",
    "sf_to_mask=[0]*31\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i%p==0:\n",
    "            if i%(p*p)==0:\n",
    "                sf_to_mask[i]=-1\n",
    "                break\n",
    "            sf_to_mask[i] |= 1<<j\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        m=1<<len(primes)\n",
    "        f=[0]*m\n",
    "        f[0]=1\n",
    "        for x in nums:\n",
    "            mask=sf_to_mask[x]\n",
    "            if mask>=0:\n",
    "                for j in range(m-1,mask-1,-1):\n",
    "                    if (j|mask)==j:\n",
    "                        f[j]=(f[j]+f[j^mask])%mod\n",
    "        return (sum(f)-1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = 1  # 质数集合是空集的方案数为 1\n",
    "        for x in nums:\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask >= 0:  # x 是 SF\n",
    "                for j in range(M - 1, mask - 1, -1):\n",
    "                    if (j | mask) == j:  # mask 是 j 的子集\n",
    "                        f[j] = (f[j] + f[j ^ mask]) % MOD  # 不选 mask + 选 mask\n",
    "        return (sum(f) - 1) % MOD  # -1 去掉空集（nums 的空子集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = 1  # 用 1 组成空质数集合的方案数\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:\n",
    "                for j in range(M - 1, -1, -1):\n",
    "                    if mask & j == 0:\n",
    "                        f[mask | j] = (f[mask | j] + f[j] * c) % MOD\n",
    "        return ((sum(f) * pow(2, cnt[1], MOD)) - 1) % MOD  # -1 表示去掉空集（nums 的空子集）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "TO_MASK = [0] * 31\n",
    "for i in range(2, 32):\n",
    "    for k, j in enumerate(PRIMES):\n",
    "        if i % j == 0:\n",
    "            if i % (j * j) == 0:\n",
    "                TO_MASK[i] = -1\n",
    "                break\n",
    "            TO_MASK[i] |= 1 << k\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        M = 1 << 10\n",
    "        MASK = [0] * 31\n",
    "        f = [0] * M\n",
    "        f[0] = 1\n",
    "        cnt = Counter(nums)\n",
    "        for x, c in cnt.items():\n",
    "            mask = TO_MASK[x]\n",
    "            if mask > 0:\n",
    "                other = (M - 1) ^ mask\n",
    "                s = other\n",
    "                while True:\n",
    "                    f[mask|s] = (f[mask|s] + f[s] * c) % mod\n",
    "                    s = (s - 1) & other\n",
    "                    if s == other:\n",
    "                        break\n",
    "                        \n",
    "        return (sum(f) * pow(2, cnt[1], mod) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    子集枚举\n",
    "\"\"\"\n",
    "mod = 1_000_000_007\n",
    "MX = 30\n",
    "isprime= [0]*(MX+1)\n",
    "primes=[] # prime\n",
    "for i in range(2,MX+1):\n",
    "    if isprime[i]== 0:\n",
    "        primes.append(i)\n",
    "        for j in range(i*i,MX+1,i):\n",
    "            isprime[j]=1\n",
    "SF = [0]*(MX+1)\n",
    "for i in range(2,MX+1):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i%(p*p) ==0:\n",
    "            SF[i]=-1\n",
    "            break\n",
    "        elif i%p==0:\n",
    "            SF[i] |= 1<<j\n",
    "        \n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        cnt =Counter(nums)\n",
    "\n",
    "        M = 1<<len(primes)\n",
    "        f = [0]*M\n",
    "        f[0]=1\n",
    "\n",
    "        for x,c in cnt.items():\n",
    "            mask =SF[x]\n",
    "            if mask > 0:\n",
    "                for j in range(M-1,mask-1,-1):\n",
    "                    if (j|mask) ==j:\n",
    "                        f[j] =(f[j] + f[j^mask]*c)%mod\n",
    "        return (sum(f) * pow(2,cnt[1],mod)-1)%mod\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "\n",
    "\n",
    "        masks = []\n",
    "\n",
    "        N = 1 << len(PRIMES)\n",
    "\n",
    "        dps = [0] * N\n",
    "\n",
    "        MOD = 1000000007\n",
    "\n",
    "        dps[0] = 1\n",
    "\n",
    "        for num in nums:\n",
    "            #print(num , '============================')\n",
    "\n",
    "            mask = 0\n",
    "            for i in range(len(PRIMES)):\n",
    "                if num % PRIMES[i] == 0:\n",
    "                    num //= PRIMES[i]\n",
    "                    if num % PRIMES[i] == 0:\n",
    "                        mask = -1\n",
    "                        break\n",
    "                    mask |= 1 << i\n",
    "\n",
    "            if mask >= 0:\n",
    "                #print(bin(mask)[2:], '-----------')\n",
    "                masks.append(mask)\n",
    "\n",
    "                for v in range(N - 1, mask - 1, -1):\n",
    "                    if (v | mask) == v:\n",
    "                        dps[v] += dps[v ^ mask]\n",
    "                        dps[v] %= MOD\n",
    "\n",
    "\n",
    "        #print(dps)\n",
    "        return (sum(dps) - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "TO_MASK = [0] * 31\n",
    "for i in range(2, 32):\n",
    "    for k, j in enumerate(PRIMES):\n",
    "        if i % j == 0:\n",
    "            if i % (j * j) == 0:\n",
    "                TO_MASK[i] = -1\n",
    "                break\n",
    "            TO_MASK[i] |= 1 << k\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        M = 1 << 10\n",
    "        MASK = [0] * 31\n",
    "        f = [0] * M\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            mask = TO_MASK[x]\n",
    "            if mask != -1:\n",
    "                for j in range(M - 1, mask - 1, -1):\n",
    "                    if (mask | j) == j:\n",
    "                        f[j] = (f[j] + f[j^mask]) % mod\n",
    "        return (sum(f) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 30\n",
    "\n",
    "can = set()\n",
    "for x in count(2):\n",
    "    if x * x > N:\n",
    "        break\n",
    "    y = x * x\n",
    "    for z in count(1):\n",
    "        if y * z > N:\n",
    "            break\n",
    "        can.add(y * z)\n",
    "\n",
    "\n",
    "def find_primes(N: int):\n",
    "    p = [True] * (N + 1)\n",
    "    p[0] = p[1] = False\n",
    "    for i in range(2, N + 1):\n",
    "        if not p[i]:\n",
    "            continue\n",
    "        for j in range(2 * i, N + 1, i):\n",
    "            p[j] = False\n",
    "    return [i for i, v in enumerate(p) if v]\n",
    "\n",
    "\n",
    "p = find_primes(N)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        a = [x for x in nums if x not in can]\n",
    "\n",
    "        cnt = Counter(a)\n",
    "        res = 0\n",
    "        one = 1\n",
    "\n",
    "        if 1 in cnt:\n",
    "            one = pow(2, cnt[1], mod)\n",
    "            del cnt[1]\n",
    "\n",
    "        a = list(cnt.keys())\n",
    "        mp = {}\n",
    "        for x in a:\n",
    "            mask = 0\n",
    "            for i, prime in enumerate(p):\n",
    "                if x % prime == 0:\n",
    "                    mask |= 1 << i\n",
    "            mp[x] = mask\n",
    "        print(mp, a)\n",
    "        n = len(a)\n",
    "        for mask in range(1, 1 << n):\n",
    "            cur = 0\n",
    "            ans = 1\n",
    "            for j in range(n):\n",
    "                if mask >> j & 1:\n",
    "                    if cur & mp[a[j]] != 0:\n",
    "                        ans = 0\n",
    "                        break\n",
    "                    cur |= mp[a[j]]\n",
    "                    ans *= cnt[a[j]]\n",
    "            # print(mask, ok, ans)\n",
    "            res = (res + ans) % mod\n",
    "\n",
    "        return (one * (res + 1) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        # 子集枚举， 状态压缩\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = pow(2, cnt[1], MOD)  # 用 1 组成空质数集合的方案数\n",
    "\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:  # x 是 SF\n",
    "                j = other = (M - 1) ^ mask  # mask 的补集\n",
    "                while True:  # 枚举 other 的子集 j\n",
    "                    f[j | mask] = (f[j | mask] + f[j] * c) % MOD  # 不选 mask + 选 mask\n",
    "                    j = (j - 1) & other\n",
    "                    if j == other: break\n",
    "        return (sum(f) - 1) % MOD  # -1 表示去掉空集（nums 的空子集）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = pow(2, cnt[1], MOD)  # 用 1 组成空质数集合的方案数\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:  # x 是 SF\n",
    "                j = other = (M - 1) ^ mask  # mask 的补集\n",
    "                while True:  # 枚举 other 的子集 j\n",
    "                    f[j | mask] = (f[j | mask] + f[j] * c) % MOD  # 不选 mask + 选 mask\n",
    "                    j = (j - 1) & other\n",
    "                    if j == other: break\n",
    "        return (sum(f) - 1) % MOD  # -1 表示去掉空集（nums 的空子集）\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)\n",
    "NSQ_TO_MASK = [0] * 31\n",
    "MOD = 10 ** 9 + 7\n",
    "M = 1 << len(PRIMES)\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:\n",
    "                NSQ_TO_MASK[i] = -1\n",
    "                break\n",
    "            NSQ_TO_MASK[i] |= 1 << j\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * M\n",
    "        dp[0] = 1\n",
    "        for i, x in enumerate(nums):\n",
    "            mask = NSQ_TO_MASK[x]\n",
    "            if mask >= 0:\n",
    "                for j in range(M - 1, -1, -1):\n",
    "                    if (j | mask) == j:\n",
    "                        dp[j] += dp[j ^ mask]\n",
    "                    dp[j] %= MOD\n",
    "        return (sum(dp) - 1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PREME=[2,3,5,7,11,13,17,19,23,29]\n",
    "MASK=[0]*31\n",
    "for n in range(2,31):\n",
    "    for i,p in enumerate(PREME):\n",
    "        if n%p==0:\n",
    "            if n % (p*p)==0:\n",
    "                MASK[n]=-1\n",
    "                break\n",
    "            MASK[n]|=(1<<i) \n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        M=1<<len(PREME)\n",
    "        dp=[0]*M\n",
    "        dp[0]=1\n",
    "        for num in nums:\n",
    "            mask=MASK[num]\n",
    "            if mask<0:\n",
    "                continue\n",
    "            for i in range(M-1,mask-1,-1):\n",
    "                if (i|mask)==i:\n",
    "                    dp[i]=(dp[i]+dp[i^mask])%MOD\n",
    "        return (sum(dp)-1)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        N, MOD = 1 << len(PRIMES), 1000000007\n",
    "        dps = [0] * N\n",
    "        dps[0] = 1\n",
    "\n",
    "        for num in nums:\n",
    "            mask = 0\n",
    "            for i in range(len(PRIMES)):\n",
    "                if num % PRIMES[i] == 0:\n",
    "                    num //= PRIMES[i]\n",
    "                    if num % PRIMES[i] == 0:\n",
    "                        mask = -1\n",
    "                        break\n",
    "                    mask |= 1 << i\n",
    "\n",
    "            if mask >= 0:\n",
    "                for v in range(N - 1, mask - 1, -1):\n",
    "                    if (v | mask) == v:\n",
    "                        dps[v] += dps[v ^ mask]\n",
    "                        dps[v] %= MOD\n",
    "\n",
    "        return (sum(dps) - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = 2,3,5,7,11,13,17,19,23,29\n",
    "m = [0]*31\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i % p == 0:\n",
    "            if i % (p*p) == 0:\n",
    "                m[i] = -1\n",
    "            else:\n",
    "                m[i] |= (1<<j)\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        print(m)\n",
    "        # [0, 0, 1, 2, -1, 4, 3, 8, -1, -1, 5, 16, 1, 32, 9, 6, -1, 64, -1, 128, 3, 10, 17, 256, 1, -1, 33, -1, 7, 512, 7]\n",
    "        nums = [x for x in nums if m[x] >= 0]\n",
    "        MOD = 10**9 + 7\n",
    "        M = (1 << len(primes)) - 1\n",
    "        f = [1] + [0]*M\n",
    "        for x in nums:\n",
    "            for j in range(M,-1,-1):\n",
    "                if (j | m[x]) == j:\n",
    "                    f[j] = (f[j] + f[j^m[x]])%MOD\n",
    "        return (sum(f) - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = 2,3,5,7,11,13,17,19,23,29\n",
    "SF_to_mask = [0]*31\n",
    "for i in range(2,31):\n",
    "    for j , p in enumerate(primes):\n",
    "        if i % p ==0:\n",
    "            if i % (p*p) == 0:\n",
    "                SF_to_mask[i] = -1\n",
    "                break\n",
    "            SF_to_mask[i] |= 1<<j            \n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        M = 1<<len(primes)\n",
    "        f = [0]*M \n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            mask = SF_to_mask[x]\n",
    "            if mask >= 0:\n",
    "                for j in range(M-1,mask-1,-1):\n",
    "                    if (j|mask) == j:\n",
    "                        f[j] = (f[j] + f[j^mask])% mod\n",
    "        return (sum(f)-1) % mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        q = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]\n",
    "        n = 2 ** len(p)\n",
    "        a = [0] * n\n",
    "        count = [0] * 31\n",
    "        for x in nums:\n",
    "            count[x] += 1\n",
    "        a[0] = 1\n",
    "        for _ in range(count[1]):\n",
    "            a[0] = a[0] * 2 % M\n",
    "        for x in range(2, 31):\n",
    "            if count[x] == 0 or x % 4 == 0 or x % 9 == 0 or x == 25:\n",
    "                continue\n",
    "            v = 0\n",
    "            for i in range(10):\n",
    "                if x % p[i] == 0:\n",
    "                    v += q[i]\n",
    "            for u in reversed(range(v, n)):\n",
    "                if u & v == v:\n",
    "                    a[u] = (a[u] + a[u-v] * count[x]) % M\n",
    "        return (sum(a) - 1) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = 1  # 质数集合是空集的方案数为 1\n",
    "        for x in nums:\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask >= 0:  # x 是 SF\n",
    "                for j in range(M - 1, mask - 1, -1):\n",
    "                    if (j | mask) == j:  # mask 是 j 的子集\n",
    "                        f[j] = (f[j] + f[j ^ mask]) % MOD  # 不选 mask + 选 mask\n",
    "        return (sum(f) - 1) % MOD  # -1 去掉空集（nums 的空子集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = [2,3,5,7,11,13,17,19,23,29]\n",
    "m = [0]*31\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i % p == 0:\n",
    "            if i % (p*p) == 0:\n",
    "                m[i] = -1\n",
    "            else:\n",
    "                m[i] |= 1 << j\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        nums = [x for x in nums if m[x] >= 0]\n",
    "        n = len(nums)\n",
    "        M = (1 << len(primes)) - 1\n",
    "        f = [1] + [0]*M\n",
    "        MOD = 10**9 + 7\n",
    "        for x in nums:\n",
    "            for j in range(M,-1,-1):\n",
    "                if (m[x] | j) == j:\n",
    "                    f[j] = (f[j] + f[j ^ m[x]]) % MOD\n",
    "        return (sum(f) - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes=2,3,5,7,11,13,17,19,23,29\n",
    "sf_to_mask=[0]*31#sf_to_mask[i] 为i的质因子集合（用二进制表示）\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i%p==0:\n",
    "            if i%(p*p)==0:#有平方因子\n",
    "                sf_to_mask[i]=-1\n",
    "                break\n",
    "            sf_to_mask[i] |= 1<<j#把j加到集合中\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        cnt=Counter(nums)\n",
    "        m=1<<len(primes)\n",
    "        f=[0]*m\n",
    "        # f[0]=1\n",
    "        # for x in nums:\n",
    "        #     mask=sf_to_mask[x]\n",
    "        #     if mask>=0:\n",
    "        #         for j in range(m-1,mask-1,-1):\n",
    "        #             if (j|mask)==j:\n",
    "        #                 f[j]=(f[j]+f[j^mask])%mod\n",
    "        # return (sum(f)-1)%mod\n",
    "        f[0]=pow(2,cnt[1],mod)\n",
    "        for x,c in cnt.items():\n",
    "            mask=sf_to_mask[x]\n",
    "            if mask>0:\n",
    "                j=other=(m-1)^mask\n",
    "                while True:\n",
    "                    f[j|mask]=(f[j|mask]+f[j]*c)%mod\n",
    "                    j=(j-1)&other\n",
    "                    if j==other:break\n",
    "        return (sum(f)-1)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)\n",
    "NSQ_TO_MASK = [0] * 31\n",
    "MOD = 10 ** 9 + 7\n",
    "M = 1 << len(PRIMES)\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:\n",
    "                NSQ_TO_MASK[i] = -1\n",
    "                break\n",
    "            NSQ_TO_MASK[i] |= 1 << j\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * M\n",
    "        dp[0] = 1\n",
    "        for i, x in enumerate(nums):\n",
    "            mask = NSQ_TO_MASK[x]\n",
    "            if mask >= 0:\n",
    "                for j in range(M - 1, mask - 1, -1):\n",
    "                    if (j | mask) == j:\n",
    "                        dp[j] = (dp[j] + dp[j ^ mask]) % MOD\n",
    "        return (sum(dp) - 1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = 1  # 质数集合是空集的方案数为 1\n",
    "        for x in nums:\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask >= 0:  # x 是 SF\n",
    "                for j in range(M - 1, mask - 1, -1):\n",
    "                    if (j | mask) == j:  # mask 是 j 的子集\n",
    "                        f[j] = (f[j] + f[j ^ mask]) % MOD  # 不选 mask + 选 mask\n",
    "        return (sum(f) - 1) % MOD  # -1 去掉空集（nums 的空子集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        m=1<<10\n",
    "        f=[0]*m\n",
    "        f[0]=1\n",
    "        for x in nums:\n",
    "            mask=SF_TO_MASK[x]\n",
    "            if mask>=0:\n",
    "                for j in range(m-1,mask-1,-1):\n",
    "                    if (j|mask)==j:\n",
    "                        f[j]=(f[j]+f[j^mask])%mod\n",
    "        return (sum(f)-1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "res = set()\n",
    "for num in range(2, 6):\n",
    "    res.add(num*num)\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        cnt = Counter(nums)\n",
    "        pre = defaultdict(int)\n",
    "        for num in cnt:\n",
    "            if num != 1 and all(num%x for x in res):\n",
    "                cur = pre.copy()\n",
    "                for p in pre:\n",
    "                    if math.gcd(p, num) == 1:\n",
    "                        cur[p*num] += pre[p]*cnt[num]\n",
    "                cur[num] += cnt[num]\n",
    "                pre = cur.copy()\n",
    "        ans = sum(pre.values())\n",
    "        ans *= pow(2, cnt[1], mod)\n",
    "        ans += pow(2, cnt[1], mod) - 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = pow(2, cnt[1], MOD)  # 用 1 组成空质数集合的方案数\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:  # x 是 SF\n",
    "                j = other = (M - 1) ^ mask  # mask 的补集\n",
    "                while True:  # 枚举 other 的子集 j\n",
    "                    f[j | mask] = (f[j | mask] + f[j] * c) % MOD  # 不选 mask + 选 mask\n",
    "                    j = (j - 1) & other\n",
    "                    if j == other: break\n",
    "        return (sum(f) - 1) % MOD  # -1 表示去掉空集（nums 的空子集）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = 1  # 质数集合是空集的方案数为 1\n",
    "        for x in nums:\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask >= 0:  # x 是 SF\n",
    "                for j in range(M - 1, mask - 1, -1):\n",
    "                    if (j | mask) == j:  # mask 是 j 的子集\n",
    "                        f[j] = (f[j] + f[j ^ mask]) % MOD  # 不选 mask + 选 mask\n",
    "        return (sum(f) - 1) % MOD  # -1 去掉空集（nums 的空子集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = 1  # 质数集合是空集的方案数为 1\n",
    "        for x in nums:\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask >= 0:  # x 是 SF\n",
    "                for j in range(M - 1, mask - 1, -1):\n",
    "                    if (j | mask) == j:  # mask 是 j 的子集\n",
    "                        f[j] = (f[j] + f[j ^ mask]) % MOD  # 不选 mask + 选 mask\n",
    "        return (sum(f) - 1) % MOD  # -1 去掉空集（nums 的空子集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x):\n",
    "    ans = set()\n",
    "    if x % 2 == 0:\n",
    "        ans.add(2)\n",
    "        while x % 2 == 0:\n",
    "            x //= 2\n",
    "    d = 3\n",
    "    while d ** 2 <= x:\n",
    "        if x % d == 0:\n",
    "            ans.add(d)\n",
    "            while x % d == 0:\n",
    "                x //= d\n",
    "        d += 2\n",
    "    if x > 1: ans.add(x)\n",
    "    return ans\n",
    "\n",
    "my_primes = defaultdict(set)\n",
    "for i in range(2, 31):\n",
    "    my_primes[i] = f(i)\n",
    "candidate = {2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30}\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        cnt1 = nums.count(1)\n",
    "        nums = list(filter(lambda p: p in candidate, nums))\n",
    "        cnt = Counter(nums)\n",
    "        L = sorted(set(nums))\n",
    "        n = len(L)\n",
    "        mod = 10 ** 9 + 7\n",
    "        rest = 0\n",
    "\n",
    "        def dfs(i, my_set, arr, val):\n",
    "            nonlocal rest\n",
    "            if i == n:\n",
    "                rest += val\n",
    "                return\n",
    "            tmp_set = f(L[i])\n",
    "            if not (tmp_set & my_set):\n",
    "                dfs(i + 1, tmp_set | my_set, arr + [L[i]], val * cnt[L[i]] % mod)\n",
    "            dfs(i + 1, my_set, arr, val)\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(i + 1, f(L[i]), [L[i]], cnt[L[i]])\n",
    "        return (pow(2, cnt1, mod) * (rest + 1) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "tmp = {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30}\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(num for num in nums if num in tmp)\n",
    "        note = Counter({1: 1})\n",
    "        for v in cnt:\n",
    "            if v != 1:\n",
    "                new_note = Counter()\n",
    "                for v1 in note:\n",
    "                    new_note[v1] += note[v1]\n",
    "                    if gcd(v, v1) == 1:\n",
    "                        new_note[v1 * v] += note[v1] * cnt[v]\n",
    "                    new_note[v1] %= mod\n",
    "                note = new_note\n",
    "        return (sum(note.values()) * pow(2, cnt[1], mod) - 1) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        div = [4, 9, 16, 25]\n",
    "        new = list()\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        for nu in nums:\n",
    "            for d in div:\n",
    "                if nu % d == 0:\n",
    "                    break\n",
    "            else:\n",
    "                new.append(nu)\n",
    "        # print(Counter(new))\n",
    "        c = list(Counter(new).items())\n",
    "        c.sort()\n",
    "        n = len(c)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        res = list()\n",
    "        ans = 0\n",
    "        # print(c)\n",
    "        def gcd(x, y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcd(y % x, x)\n",
    "        # print(gcd(7, 11))\n",
    "        # print(gcd(2, 7))\n",
    "        # print(gcd(2, 11))\n",
    "        def check(i):\n",
    "            for nu in res:\n",
    "                # print(c[i][0], nu, gcd(nu, c[i][0]))\n",
    "                # print(i, n)\n",
    "                # print(c)\n",
    "                if gcd(nu, c[i][0]) != 1:\n",
    "                    return False\n",
    "            # print(\"i:\", i)\n",
    "            return True\n",
    "        mod = (10 ** 9 + 7)\n",
    "        def dfs(i, last):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                return\n",
    "            # print(\"check(i)\", i, check(i))\n",
    "            if check(i):\n",
    "                res.append(c[i][0])\n",
    "                tmp = last * c[i][1] % mod\n",
    "                ans += tmp\n",
    "                # print(res, tmp, ans)\n",
    "                dfs(i + 1, tmp)\n",
    "                res.pop()\n",
    "            dfs(i + 1, last)\n",
    "        if c[0][0] == 1:\n",
    "            dfs(1, 1)\n",
    "            ans = pow(2, c[0][1], mod) * (ans + 1) % mod\n",
    "            ans = (ans - 1) % mod\n",
    "        else:\n",
    "            dfs(0, 1)\n",
    "        return ans % mod\n",
    "            \n",
    "                \n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        #如何表示数字\n",
    "        #用二进制表示哪些数可以由质数表示\n",
    "        prime=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        NSQ_MASK=[0]*31\n",
    "        #把每个数对应的质因子集合表示成二进制数\n",
    "        #枚举每个数\n",
    "        for i in range(2,31):\n",
    "            for j,p in enumerate(prime):\n",
    "                if i%p==0:\n",
    "                    if i%(p*p)==0:\n",
    "                        NSQ_MASK[i]=-1\n",
    "                        break\n",
    "                    NSQ_MASK[i]|=(1<<j)\n",
    "        #枚举子集的元素乘积，把元素乘积看成背包。去装能组成这个乘积的NSQ\n",
    "        MOD=int(1e9+7)\n",
    "        M=1<<len(prime)\n",
    "        f=[0]*M\n",
    "        f[0]=1\n",
    "        for i,x in enumerate(nums):\n",
    "            mask=NSQ_MASK[x]#取到了这个数对应的质因数集合\n",
    "            if mask>=0:\n",
    "                for j in range(M-1, mask-1,-1):\n",
    "                    if (mask|j) ==j:#mask是j的子集\n",
    "                        f[j]=(f[j]+f[j^mask])%MOD\n",
    "        return (sum(f)-1)%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "tmp = {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30}\n",
    "mod = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums) -> int:\n",
    "        cnt = Counter(num for num in nums if num in tmp)\n",
    "        note = Counter({1: 1})\n",
    "        for v in cnt:\n",
    "            if v != 1:\n",
    "                new_note = Counter()\n",
    "                for v1 in note:\n",
    "                    new_note[v1] += note[v1]\n",
    "                    if gcd(v, v1) == 1:\n",
    "                        new_note[v1 * v] += note[v1] * cnt[v]\n",
    "                    new_note[v1] %= mod\n",
    "                note = new_note\n",
    "        return (sum(note.values()) * pow(2, cnt[1], mod) - 1) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES=2,3,5,7,11,13,17,19,23,29\n",
    "SF_TO_MASK=[0]*31\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(PRIMES):\n",
    "        if i%p==0:\n",
    "            if i % (p*p)==0:\n",
    "                SF_TO_MASK[i]=-1\n",
    "                break  \n",
    "            SF_TO_MASK[i]|=1<<j\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        M=1<<len(PRIMES) \n",
    "        f=[0]*M     #f[j]表示恰好组成质数集合j的方案数\n",
    "        f[0]=1\n",
    "        cnt=Counter(nums)\n",
    "        for x,c in cnt.items():\n",
    "            mask=SF_TO_MASK[x]\n",
    "            if mask>0:\n",
    "                for other in range(M-1,-1,-1):\n",
    "                    if (mask&other)==0:\n",
    "                        f[mask|other]=(f[other|mask]+f[other]*c)%MOD  \n",
    "        return (sum(f)*pow(2,cnt[1],MOD)-1)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        pn = len(primes)\n",
    "        dp = [0] * (1 << pn)\n",
    "        dp[0] = 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for x in nums:\n",
    "            mask = 0\n",
    "            for i in range(pn):\n",
    "                cnt = 0\n",
    "                while x % primes[i] == 0:\n",
    "                    x /= primes[i]\n",
    "                    cnt += 1\n",
    "                if cnt > 1:\n",
    "                    break\n",
    "                elif cnt == 1:\n",
    "                    mask |= 1 << i\n",
    "            else:\n",
    "                for i in range(1 << pn):\n",
    "                    if not i & mask:\n",
    "                        dp[i | mask] = (dp[i | mask] + dp[i]) % MOD\n",
    "        return (sum(dp) - 1) % MOD\n",
    "                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = 2,3,5,7,11,13,17,19,23,29\n",
    "m = [0]*31\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i % p == 0:\n",
    "            if i % (p*p) == 0:\n",
    "                m[i] = -1\n",
    "                break\n",
    "            else:\n",
    "                m[i] += (1<<j)\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        nums = [x for x in nums if m[x] >= 0]\n",
    "        MOD = 10**9 + 7\n",
    "        M = (1 << len(primes)) - 1\n",
    "        f = [1] + [0]*M\n",
    "        for x in nums:\n",
    "            for j in range(M,-1,-1):\n",
    "                if (j | m[x]) == j:\n",
    "                    f[j] = (f[j] + f[j^m[x]])%MOD\n",
    "        return (sum(f) - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        prime=[2,3,5,7,11,13,17,19,23,29]\n",
    "        toprime=[0]*31\n",
    "        for i in range(2,31):\n",
    "            for j,k in enumerate(prime):\n",
    "                if i<k:\n",
    "                    break\n",
    "                if i%k==0:\n",
    "                    if i%(k*k)==0:\n",
    "                        toprime[i]=-1\n",
    "                        break\n",
    "                    toprime[i]|=1<<j\n",
    "        mod=pow(10,9)+7\n",
    "        m=1<<10\n",
    "        f=[0]*m\n",
    "        f[0]=1\n",
    "        for x in nums:\n",
    "            tp=toprime[x]\n",
    "            if tp>=0:\n",
    "                for j in range(m-1,tp-1,-1):\n",
    "                    if (j|tp)==j:\n",
    "                        f[j]=(f[j]+f[j^tp])%mod\n",
    "        return (sum(f)-1+mod)%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        modnum = 10**9+7\n",
    "        pri = [2,3,5,7,11,13,17,19,23,29]\n",
    "        allstatus = 1<<10\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(allstatus)]\n",
    "        sqnum = set()\n",
    "        dp[0] = 1\n",
    "        numsta = {}\n",
    "        for i in range(1, 31):\n",
    "            status = 0\n",
    "            for j in range(len(pri)):\n",
    "                if i % pri[j] == 0:\n",
    "                    status |= (1<<j)\n",
    "            numsta[i] = status\n",
    "        for i in range(2, 31):\n",
    "            for j in range(1, 31):\n",
    "                if i*i*j > 30:\n",
    "                    break\n",
    "                sqnum.add(i*i*j)\n",
    "        for i in range(n):\n",
    "            for status in range(allstatus-1, -1, -1):\n",
    "                numstatus = numsta[nums[i]]\n",
    "                if numstatus & status == numstatus and nums[i] not in sqnum:\n",
    "                    dp[status] = (dp[status] + dp[numstatus^status]) % modnum\n",
    "        return (sum(dp)-1)%modnum\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = pow(2, cnt[1], MOD)  # 用 1 组成空质数集合的方案数\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:  # x 是 SF\n",
    "                j = other = (M - 1) ^ mask  # mask 的补集\n",
    "                while True:  # 枚举 other 的子集 j\n",
    "                    f[j | mask] = (f[j | mask] + f[j] * c) % MOD  # 不选 mask + 选 mask\n",
    "                    j = (j - 1) & other\n",
    "                    if j == other: break\n",
    "        return (sum(f) - 1) % MOD  # -1 表示去掉空集（nums 的空子集）\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n",
    "SF_TO_MASK = [0] * 31  # SF_TO_MASK[i] 为 i 的质因子集合（用二进制表示）\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:  # 有平方因子\n",
    "                SF_TO_MASK[i] = -1\n",
    "                break\n",
    "            SF_TO_MASK[i] |= 1 << j  # 把 j 加到集合中\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1 << len(PRIMES)\n",
    "        f = [0] * M  # f[j] 表示恰好组成质数集合 j 的方案数\n",
    "        f[0] = pow(2, cnt[1], MOD)  # 用 1 组成空质数集合的方案数\n",
    "        for x, c in cnt.items():\n",
    "            mask = SF_TO_MASK[x]\n",
    "            if mask > 0:  # x 是 SF\n",
    "                j = other = (M - 1) ^ mask  # mask 的补集\n",
    "                while True:  # 枚举 other 的子集 j\n",
    "                    f[j | mask] = (f[j | mask] + f[j] * c) % MOD  # 不选 mask + 选 mask\n",
    "                    j = (j - 1) & other\n",
    "                    if j == other: break\n",
    "        return (sum(f) - 1) % MOD  # -1 表示去掉空集（nums 的空子集）\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = 2,3,5,7,11,13,17,19,23,29\n",
    "m = [0]*31\n",
    "for i in range(2,31):\n",
    "    for j,p in enumerate(primes):\n",
    "        if i % p == 0:\n",
    "            if i % (p*p) == 0:\n",
    "                m[i] = -1\n",
    "                break\n",
    "            else:\n",
    "                m[i] += (1<<j)\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        nums = [x for x in nums if m[x] >= 0]\n",
    "        MOD = 10**9 + 7\n",
    "        cnt = Counter(nums)\n",
    "        M = 1<<len(primes)\n",
    "        f = [0]*M\n",
    "        f[0] = pow(2,cnt[1],MOD)\n",
    "        for x,c in cnt.items():\n",
    "            mask = m[x]\n",
    "            if mask > 0:\n",
    "                j = other = (M - 1) ^ mask\n",
    "                while True:\n",
    "                    f[j | mask] = (f[j | mask] + f[j]*c) % MOD\n",
    "                    j = (j - 1)&other\n",
    "                    if j == other:\n",
    "                        break\n",
    "        return (sum(f) - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums) -> int:\n",
    "        A=[2,3,5,7,11,13,17,19,23,29]\n",
    "        dic=dict()\n",
    "        for i in range(1,31):\n",
    "            dic[i]=0\n",
    "        for i in nums:\n",
    "            for j in {4,9}:\n",
    "                if i%j==0:\n",
    "                    break\n",
    "            if i%j==0:\n",
    "                continue\n",
    "            dic[i]=dic[i]+1\n",
    "        memo=dict()\n",
    "        def find(x):\n",
    "            if x in memo:\n",
    "                return memo[x]\n",
    "            if x==0:\n",
    "                return 1\n",
    "            ans=0\n",
    "            i=0\n",
    "            while x&1<<i==0:i+=1\n",
    "            if i==0:\n",
    "                s=x-1\n",
    "                if x&2!=0:\n",
    "                    ans+=find(s-2)*dic[6]%(10**9+7)\n",
    "                    if x&4!=0:\n",
    "                        ans+=find(s-6)*dic[30]%(10**9+7)\n",
    "                if x&(1<<2)!=0:\n",
    "                    ans+=find(s-4)*dic[10]%(10**9+7)\n",
    "                if x&(1<<3)!=0:\n",
    "                    ans+=find(s-8)*dic[14]%(10**9+7)\n",
    "                if x&(1<<4)!=0:\n",
    "                    ans+=find(s-16)*dic[22]%(10**9+7)\n",
    "                if x&(1<<5)!=0:\n",
    "                    ans+=find(s-32)*dic[26]%(10**9+7)\n",
    "            if i==1:\n",
    "                s=x-2\n",
    "                if x&(1<<2)!=0:\n",
    "                    ans+=find(s-4)*dic[15]%(10**9+7)\n",
    "                if x&(1<<3)!=0:\n",
    "                    ans+=find(s-8)*dic[21]%(10**9+7)\n",
    "            ans+=find(x-(1<<i))*dic[A[i]]%(10**9+7)\n",
    "            memo[x]=ans\n",
    "            return memo[x]\n",
    "        for i in range(1,1024):\n",
    "            find(i)\n",
    "        Sum=0\n",
    "        for i in memo:\n",
    "            Sum+=memo[i]\n",
    "        Sum=Sum%(10**9+7)\n",
    "        return ((Sum+1)*(2**dic[1])-1)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums) -> int:\n",
    "        A=[2,3,5,7,11,13,17,19,23,29]\n",
    "        dic=dict()\n",
    "        for i in range(1,31):\n",
    "            dic[i]=0\n",
    "        for i in nums:\n",
    "            for j in {4,9}:\n",
    "                if i%j==0:\n",
    "                    break\n",
    "            if i%j==0:\n",
    "                continue\n",
    "            dic[i]=dic[i]+1\n",
    "        memo=dict()\n",
    "        def find(x):\n",
    "            if x in memo:\n",
    "                return memo[x]\n",
    "            if x==0:\n",
    "                return 1\n",
    "            ans=0\n",
    "            i=0\n",
    "            while x&1<<i==0:i+=1\n",
    "            if i==0:\n",
    "                s=x-1\n",
    "                if x&2!=0:\n",
    "                    ans+=find(s-2)*dic[6]%(10**9+7)\n",
    "                    if x&4!=0:\n",
    "                        ans+=find(s-6)*dic[30]%(10**9+7)\n",
    "                if x&(1<<2)!=0:\n",
    "                    ans+=find(s-4)*dic[10]%(10**9+7)\n",
    "                if x&(1<<3)!=0:\n",
    "                    ans+=find(s-8)*dic[14]%(10**9+7)\n",
    "                if x&(1<<4)!=0:\n",
    "                    ans+=find(s-16)*dic[22]%(10**9+7)\n",
    "                if x&(1<<5)!=0:\n",
    "                    ans+=find(s-32)*dic[26]%(10**9+7)\n",
    "            if i==1:\n",
    "                s=x-2\n",
    "                if x&(1<<2)!=0:\n",
    "                    ans+=find(s-4)*dic[15]%(10**9+7)\n",
    "                if x&(1<<3)!=0:\n",
    "                    ans+=find(s-8)*dic[21]%(10**9+7)\n",
    "            ans+=find(x-(1<<i))*dic[A[i]]%(10**9+7)\n",
    "            memo[x]=ans\n",
    "            return memo[x]\n",
    "        for i in range(1,1024):\n",
    "            find(i)\n",
    "        Sum=0\n",
    "        for i in memo:\n",
    "            Sum+=memo[i]\n",
    "        Sum=Sum%(10**9+7)\n",
    "        return ((Sum+1)*(2**dic[1])-1)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        def decomposite(num):\n",
    "            res = 0\n",
    "            for j, p in enumerate(prime):\n",
    "                if num % p == 0:\n",
    "                    res |= (1<<j)\n",
    "            return res\n",
    "        prime=[2,3,5,7,11,13,17,19,23,29]\n",
    "        def check(num):\n",
    "            if num==1:\n",
    "                return False\n",
    "            for p in prime:\n",
    "                if num%(p**2)==0: return False\n",
    "            return True\n",
    "        #将每个非平方数分解为质因数形式,因为非平方所以每个质因数存在状态只有两种：有或没有,经典状压\n",
    "        #状态压缩,将质因数的存在情况用二进制数表达\n",
    "        cnt=Counter(nums)\n",
    "        count_1=cnt[1]\n",
    "        cnt=[(i,v) for i,v in cnt.items() if check(i)]\n",
    "        m=len(cnt)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==m: return 1\n",
    "            res=0\n",
    "            #不选\n",
    "            res+=dfs(i+1,mask)\n",
    "            #选\n",
    "            new_mask=0\n",
    "            num=cnt[i][0]\n",
    "            new_mask=decomposite(num)\n",
    "            if new_mask&mask==0:\n",
    "                res+=dfs(i+1,new_mask|mask)*cnt[i][1] #次数\n",
    "            res%=MOD\n",
    "            return res\n",
    "        #需要特殊考虑1的情况\n",
    "        return (dfs(0,0)*(2**count_1)-1)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mod=10**9+7\n",
    "        count1=nums.count(1)\n",
    "        sett=set()\n",
    "\n",
    "        def fenjie(n):\n",
    "            temp=2\n",
    "            l=[]\n",
    "            while temp*temp<=n:\n",
    "                while n%temp==0:\n",
    "                    l.append(temp)\n",
    "                    n//=temp\n",
    "                temp+=1\n",
    "            if n>1:l.append(n)\n",
    "            return Counter(l)\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos,s):\n",
    "            if pos==n:return int(s!=0)\n",
    "            ans=0\n",
    "            if s|ll[pos]<s+ll[pos]:\n",
    "                ans+=dfs(pos+1,s)\n",
    "            else:\n",
    "                ans+=dfs(pos+1,s)\n",
    "                ans+=dfs(pos+1,s|ll[pos])*dicc[ll[pos]]\n",
    "\n",
    "            return ans%mod\n",
    "\n",
    "        num=[]\n",
    "        for i in nums:\n",
    "            if i==1:\n",
    "                continue\n",
    "            dicc=fenjie(i)\n",
    "            maxx=max(dicc.values())\n",
    "            if maxx==1:\n",
    "                num.append(i)\n",
    "\n",
    "        nums=num.copy()\n",
    "        del num\n",
    "\n",
    "        for i in nums:\n",
    "            l=fenjie(i)\n",
    "            for j in l:sett.add(j)\n",
    "        l=list(sett)\n",
    "        del sett\n",
    "\n",
    "        toindex=dict()\n",
    "        for i in range(len(l)):\n",
    "            toindex[l[i]]=i\n",
    "\n",
    "        ll=[]\n",
    "        dicc=Counter()\n",
    "        for i in nums:\n",
    "            l=list(fenjie(i).keys())\n",
    "            s=0\n",
    "            for j in l:\n",
    "                index=toindex[j]\n",
    "                s|=1<<index\n",
    "            if s not in ll:\n",
    "                ll.append(s)\n",
    "            dicc[s]+=1\n",
    "        n=len(ll)\n",
    "        ans=(dfs(0,0)*pow(2,count1,mod)+pow(2,count1,mod)-1) if dfs(0,0) else (pow(2,count1,mod)-1)\n",
    "        return ans%mod\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        sq = [4, 9, 16, 25]\n",
    "        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        cnts = collections.Counter(nums)\n",
    "        cnt1 = cnts[1]\n",
    "        for k in list(cnts.keys()):\n",
    "            if min([k%s for s in sq])==0 or k==1:\n",
    "                del(cnts[k])\n",
    "        l = list(cnts.keys())\n",
    "        print(l)\n",
    "        @cache\n",
    "        def dfs(flag, index):\n",
    "            if index==len(l):\n",
    "                return 1\n",
    "            ans = dfs(flag, index+1)\n",
    "            for i in range(len(prime)):\n",
    "                if l[index]%prime[i]==0:\n",
    "                    if flag & 1<<i > 0 :\n",
    "                        return ans\n",
    "                    flag |= 1<<i\n",
    "            return ans + dfs(flag, index+1)*cnts[l[index]]\n",
    "        return (dfs(0, 0) * (1<<cnt1) - 1) % (10**9+7)\n",
    "        # v = [1] + list(cnts.values())\n",
    "        # return (reduce(lambda x, y: x*(y+1), v) - 1)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        prime=[2,3,5,7,11,13,17,19,23,29]\n",
    "        def check(num):\n",
    "            if num==1:\n",
    "                return False\n",
    "            for p in prime:\n",
    "                if num%(p**2)==0: return False\n",
    "            return True\n",
    "        #将每个非平方数分解为质因数形式,因为非平方所以每个质因数存在状态只有两种：有或没有,经典状压\n",
    "        #状态压缩,将质因数的存在情况用二进制数表达\n",
    "        cnt=Counter(nums)\n",
    "        count_1=cnt[1]\n",
    "        cnt=[(i,v) for i,v in cnt.items() if check(i)]\n",
    "        m=len(cnt)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==m: return 1\n",
    "            res=0\n",
    "            #不选\n",
    "            res+=dfs(i+1,mask)\n",
    "            #选\n",
    "            new_mask,num=0,cnt[i][0]\n",
    "            for j,p in enumerate(prime):\n",
    "                if num%p==0: new_mask|=(1<<j)\n",
    "            if new_mask&mask==0:\n",
    "                res+=dfs(i+1,new_mask|mask)*cnt[i][1] #次数\n",
    "            res%=MOD\n",
    "            return res\n",
    "        #需要特殊考虑1的情况\n",
    "        return (dfs(0,0)*(2**count_1)-1)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        prime=[2,3,5,7,11,13,17,19,23,29]\n",
    "        def check(num):\n",
    "            if num==1:\n",
    "                return False\n",
    "            for p in prime:\n",
    "                if num%(p**2)==0: return False\n",
    "            return True\n",
    "        #将每个非平方数分解为质因数形式,因为非平方所以每个质因数存在状态只有两种：有或没有,经典状压\n",
    "        #状态压缩,将质因数的存在情况用二进制数表达\n",
    "        cnt=Counter(nums)\n",
    "        count_1=cnt[1]\n",
    "        cnt=[(i,v) for i,v in cnt.items() if check(i)]\n",
    "        m=len(cnt)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==m: return 1\n",
    "            res=0\n",
    "            #不选\n",
    "            res+=dfs(i+1,mask)\n",
    "            #选\n",
    "            new_mask,num=0,cnt[i][0]\n",
    "            for j,p in enumerate(prime):\n",
    "                if num%p==0: new_mask|=(1<<j)\n",
    "            if new_mask&mask==0:\n",
    "                res+=dfs(i+1,new_mask|mask)*cnt[i][1] #次数\n",
    "            res%=MOD\n",
    "            return res\n",
    "        #需要特殊考虑1的情况\n",
    "        return (dfs(0,0)*(2**count_1)-1)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, a: List[int]) -> int:\n",
    "        p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        b=[]\n",
    "        for t in a:\n",
    "            if all(t%(i*i)!=0 for i in [2,3,5]):\n",
    "                b.append(0)\n",
    "                for k1,k2 in enumerate(p):\n",
    "                    if t%k2==0:\n",
    "                        b[-1]|=1<<k1\n",
    "        n=len(b)\n",
    "        mod=10**9+7\n",
    "        dp=[[0]*1050 for i in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(n):\n",
    "            for j in range(len(dp[0])):\n",
    "                dp[i+1][j]=dp[i][j]\n",
    "                if (j&b[i])==b[i]:\n",
    "                    dp[i+1][j]=(dp[i+1][j]+dp[i][j^b[i]])%mod\n",
    "        return (sum(dp[-1])-1+mod)%mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        pn = len(primes)\n",
    "        \n",
    "        # delete the num which is a square-free integer.\n",
    "        a = []\n",
    "        for x in nums:\n",
    "            ok = True\n",
    "            for y in range(2, int(sqrt(max(nums)) + 1)):\n",
    "                if x % (y * y) == 0:\n",
    "                    ok = False\n",
    "                    break\n",
    "            if ok == True:\n",
    "                a.append(x)\n",
    "        n = len(a)\n",
    "        \n",
    "        # dp[i]:enumerate the all combination of 10 primes\n",
    "        dp = [[0 for _ in range(1 << pn)] for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i, x in enumerate(a):\n",
    "            for state in range(1 << pn):\n",
    "                dp[i + 1][state] = dp[i][state]\n",
    "\n",
    "            mask = 0\n",
    "            for pi, prime in enumerate(primes):\n",
    "                if x % prime == 0:\n",
    "                    mask |= (1 << pi)\n",
    "            \n",
    "            for state in range(1 << pn):\n",
    "                if (state & mask) == 0:\n",
    "                    nxt_state = state | mask\n",
    "                    dp[i + 1][nxt_state] += dp[i][state]\n",
    "                    dp[i + 1][nxt_state] %= MOD\n",
    "        \n",
    "        res = 0\n",
    "        for state in range(1 << pn):\n",
    "            res += dp[n][state]\n",
    "            res %= MOD\n",
    "        res = (res - 1 + MOD) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        primes = [2,3,5,7,11,13,17,19,23,29]\n",
    "        n = len(nums)\n",
    "        dp = [[0] * ( 1 << 10) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        def check(x):\n",
    "            for i in range(10):\n",
    "                if x % (primes[i] * primes[i]) == 0:\n",
    "                    return True \n",
    "            return False \n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            mask = 0 \n",
    "            for j in range(10):\n",
    "                if nums[i-1] % primes[j] == 0:\n",
    "                    mask |= (1 << j)\n",
    "            #print(mask)\n",
    "            for j in range(1 <<10):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "            if check(nums[i-1]):\n",
    "                continue\n",
    "            for j in range(1 <<10):\n",
    "                if mask & j == 0:\n",
    "                    dp[i][j|mask] = (dp[i][j|mask] + dp[i-1][j]) % mod\n",
    "        \n",
    "        ans = 0 \n",
    "        for i in range(1 << 10):\n",
    "            ans = (ans + dp[n][i]) % mod\n",
    " \n",
    "        return (ans + mod - 1) % mod \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        d = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        cant = [4, 8, 12, 16, 20, 24, 28, 9, 18, 27, 25]\n",
    "        n = len(nums)\n",
    "        dp = [[0] * 1024 for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        cnt1 = nums.count(1)\n",
    "        for i in range(1, n + 1):\n",
    "            cur = nums[i - 1]\n",
    "            dp[i] = dp[i - 1][:]\n",
    "            if cur in cant:\n",
    "                continue\n",
    "            tmp = 0\n",
    "            for j, num in enumerate(d):\n",
    "                if cur % num == 0:\n",
    "                    tmp |= 1 << j\n",
    "            for mask in range(1024):\n",
    "                if mask & tmp == 0:     \n",
    "                    dp[i][mask | tmp] += dp[i - 1][mask]\n",
    "        # print(dp[-1])\n",
    "        return (sum(dp[-1]) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        d = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        cant = [4, 8, 12, 16, 20, 24, 28, 9, 18, 27, 25]\n",
    "        n = len(nums)\n",
    "        dp = [[0] * 1024 for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        cnt1 = nums.count(1)\n",
    "        for i in range(1, n + 1):\n",
    "            cur = nums[i - 1]\n",
    "            dp[i] = dp[i - 1][:]\n",
    "            if cur in cant:\n",
    "                continue\n",
    "            tmp = 0\n",
    "            for j, num in enumerate(d):\n",
    "                if cur % num == 0:\n",
    "                    tmp |= 1 << j\n",
    "            for mask in range(1024):\n",
    "                if mask & tmp == 0:     \n",
    "                    dp[i][mask | tmp] += dp[i - 1][mask]\n",
    "        # print(dp[-1])\n",
    "        return (sum(dp[-1][1:]) + pow(2, cnt1, mod) - 1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        dic = [2,3,5,7,11,13,17,19,23,29]\n",
    "        n = len(nums)\n",
    "        dp = [[0]*(1<<11) for _ in range(n)]\n",
    "        for i,num in enumerate(nums):\n",
    "            if i > 0:\n",
    "                dp[i] = dp[i-1][::]\n",
    "            if num % 4==0 or num % 9 == 0 or num%25 == 0:\n",
    "                continue\n",
    "            curSts = 0\n",
    "            for p in dic:\n",
    "                if num%p == 0:\n",
    "                    curSts += 1\n",
    "                curSts <<= 1\n",
    "            #print(curSts)\n",
    "            dp[i][curSts] += 1\n",
    "            if i == 0:\n",
    "                continue\n",
    "            j = 1<<11\n",
    "            while j:\n",
    "                j = (j-1)&(~curSts)\n",
    "                dp[i][curSts|j] += dp[i-1][j]\n",
    "        #print(dp[-1])\n",
    "        return sum(dp[-1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)\n",
    "NSQ_TO_MASK = [0] * 31\n",
    "MOD = 10 ** 9 + 7\n",
    "M = 1 << len(PRIMES)\n",
    "for i in range(2, 31):\n",
    "    for j, p in enumerate(PRIMES):\n",
    "        if i % p == 0:\n",
    "            if i % (p * p) == 0:\n",
    "                NSQ_TO_MASK[i] = -1\n",
    "                break\n",
    "            NSQ_TO_MASK[i] |= 1 << j\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * M for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = 1\n",
    "        for i, x in enumerate(nums):\n",
    "            mask = NSQ_TO_MASK[x]\n",
    "            if mask >= 0:\n",
    "                for j in range(M):\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                    if (j | mask) == j:\n",
    "                        dp[i + 1][j] += dp[i][j ^ mask]\n",
    "                    dp[i + 1][j] %= MOD\n",
    "            else:\n",
    "                dp[i + 1] = dp[i]\n",
    "        return (sum(dp[n]) - 1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        t = [2,3,5,7,11,13,17,19,23,29]\n",
    "        m = len(t)\n",
    "        n = len(nums)\n",
    "        dp = [[0] * (1 << m) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        Mod = int(1e9+7)\n",
    "        for i in range(1, n+1):\n",
    "            mask = 0 \n",
    "            flag = 1\n",
    "            for k in range(m):\n",
    "                if nums[i-1] % t[k] == 0:\n",
    "                    if nums[i-1] % (t[k] * t[k])== 0:\n",
    "                        flag = 0\n",
    "                        mask = 0 \n",
    "                        break \n",
    "                    mask |= 1 << k\n",
    "            if nums[i-1] == 1:\n",
    "                flag = 1\n",
    "                mask = 0 \n",
    "            for j in range(1 << m): \n",
    "                if flag == 1 and (j & mask) == mask:\n",
    "                    dp[i][j] = (dp[i-1][j] + dp[i-1][j ^ mask]) % Mod\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] % Mod\n",
    "        \n",
    "        return (sum(dp[n]) - 1) % Mod \n",
    "    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        modnum = 10**9+7\n",
    "        pri = [1,2,3,5,7,11,13,17,19,23,29]\n",
    "        allstatus = 1<<11\n",
    "        n = len(nums)\n",
    "        dp = [[0 for _ in range(allstatus)] for _ in range(n+1)]\n",
    "        sqnum = set()\n",
    "        dp[0][0] = 1\n",
    "        numsta = {}\n",
    "        for i in range(1, 31):\n",
    "            status = 0\n",
    "            for j in range(len(pri)):\n",
    "                if i % pri[j] == 0:\n",
    "                    status |= (1<<j)\n",
    "            numsta[i] = status\n",
    "        for i in range(2, 31):\n",
    "            for j in range(1, 31):\n",
    "                if i*i*j > 30:\n",
    "                    break\n",
    "                sqnum.add(i*i*j)\n",
    "        for i in range(n):\n",
    "            for status in range(allstatus):\n",
    "                numstatus = numsta[nums[i]]\n",
    "                dp[i+1][status] += dp[i][status]\n",
    "                if (numstatus & status == 0 or numstatus & status == 1) and nums[i] not in sqnum:\n",
    "                    dp[i+1][numstatus|status] = (dp[i+1][numstatus|status] + dp[i][status]) % modnum\n",
    "        return sum(dp[n][i] for i in range(1, allstatus))%modnum\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        is_primes = [True] * 31\n",
    "        for i in range(2, 31):\n",
    "            if is_primes[i]:\n",
    "                for j in range(i * i, 31, i):\n",
    "                    is_primes[j] = False\n",
    "        dic = collections.defaultdict(int)\n",
    "        cnt = 0\n",
    "        for i in range(1, 31):\n",
    "            if is_primes[i]:\n",
    "                dic[i] = cnt\n",
    "                cnt += 1\n",
    "        masks = [0] * 31\n",
    "        for i in range(1, 31):\n",
    "            if is_primes[i]:\n",
    "                masks[i] = 1 << dic[i]\n",
    "            elif i % 4 == 0 or i % 9 == 0 or i % 25 == 0:\n",
    "                masks[i] = -1\n",
    "            else:\n",
    "                for j in range(2, 31):\n",
    "                    if is_primes[j] and i % j == 0:\n",
    "                        masks[i] |= 1 << dic[j]\n",
    "        cnts = [0] * 31\n",
    "        for num in nums:\n",
    "           cnts[num] += 1\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "           if i == 31:\n",
    "               return 1 if j > 0 else 0\n",
    "           res = dfs(i + 1, j)\n",
    "           if i == 1:\n",
    "              res += (pow(2, cnts[i], MOD) - 1) * dfs(i + 1, j | 1) % MOD\n",
    "              res %= MOD\n",
    "           elif masks[i] != -1 and (masks[i] & j) == 0:\n",
    "              res += cnts[i] * dfs(i + 1, masks[i] | j)\n",
    "         #   if nums[i] == 1 or masks[nums[i]] != -1 and (j & masks[nums[i]]) == 0:\n",
    "         #       res += dfs(i + 1, j | masks[nums[i]])\n",
    "         #       res %= MOD\n",
    "         #   memo[i][j] = res\n",
    "           return res\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def squareFreeSubsets(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        primes = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i, p in enumerate(primes):\n",
    "           dic[p] = i\n",
    "        masks = [0] * 31\n",
    "        for i in range(1, 31):\n",
    "            if i in dic.keys():\n",
    "                masks[i] = 1 << dic[i]\n",
    "            elif i % 4 == 0 or i % 9 == 0 or i % 25 == 0:\n",
    "                masks[i] = -1\n",
    "            else:\n",
    "                for j in range(2, 31):\n",
    "                    if j in dic.keys() and i % j == 0:\n",
    "                        masks[i] |= 1 << dic[j]\n",
    "        cnts = [0] * 31\n",
    "        for num in nums:\n",
    "           cnts[num] += 1\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "           if i == 31:\n",
    "               return 1 if j > 0 else 0\n",
    "           res = dfs(i + 1, j)\n",
    "           if i == 1:\n",
    "              res += (pow(2, cnts[i], MOD) - 1) * dfs(i + 1, j | 1) % MOD\n",
    "           elif masks[i] != -1 and (masks[i] & j) == 0:\n",
    "              res += cnts[i] * dfs(i + 1, masks[i] | j)\n",
    "           return res % MOD\n",
    "        return dfs(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
